{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<center>\n",
    "<img src=\"../../img/ods_stickers.jpg\">\n",
    "    \n",
    "## Открытый курс по машинному обучению [mlcourse.ai](https://mlcourse.ai)\n",
    "\n",
    "Автор материала: Data Scientist @ Zeptolab, лектор в Центре Математических Финансов МГУ Дмитрий Сергеев. Материал распространяется на условиях лицензии [Creative Commons CC BY-NC-SA 4.0](https://creativecommons.org/licenses/by-nc-sa/4.0/). Можно использовать в любых целях (редактировать, поправлять и брать за основу), кроме коммерческих, но с обязательным упоминанием автора материала."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <center>Тема 9. Анализ временных рядов в Python</center>\n",
    "## <center>Часть 1. Главная</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Доброго дня!\n",
    "\n",
    "Мы продолжаем наш цикл статей открытого курса по машинному обучению и сегодня поговорим о временных рядах. \n",
    "\n",
    "Посмотрим на то, как с ними работать в Python, какие возможные методы и модели можно использовать для прогнозирования; что такое двойное и тройное экспоненциальное взвешивание; что делать, если стационарность - это не про вас; как построить SARIMA и не умереть; и как прогнозировать xgboost-ом. И всё это будем применять к примеру из суровой реальности."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# План:\n",
    "\n",
    "1. Движемся, сглаживаем и оцениваем\n",
    "    - Rolling window estimations\n",
    "    - Экспоненциальное сглаживание, модель Хольта-Винтерса\n",
    "    - Кросс-валидация на временных рядах, подбор параметров\n",
    "2. Эконометрический подход\n",
    "    - Стационарность, единичные корни\n",
    "    - Избавляемся от нестационарности и строим SARIMA\n",
    "3. Линейные и не очень модели на временных рядах\n",
    "    - Извлечение признаков (Feature extraction)\n",
    "    - Линейная регрессия vs XGBoost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "На работе я практически ежедневно сталкиваюсь с теми или иными задачами, связанными с временными рядам. Чаще всего возникает вопрос - а что у нас будет происходить с нашими показателями в ближайший день/неделю/месяц/пр. - сколько игроков установят приложения, сколько будет онлайна, как много действий совершат пользователи, и так далее. К задаче прогнозирования можно подходить по-разному, в зависимости от того, какого качества должен быть прогноз, на какой период мы хотим его строить, и, конечно, как долго нужно подбирать и настраивать параметры модели для его получения. \n",
    "\n",
    "Начнем с простых методов анализа и прогнозирования - скользящих средних, сглаживаний и их вариаций."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Движемся, сглаживаем и оцениваем\n",
    "\n",
    "Небольшое [определение](https://ru.wikipedia.org/wiki/Временной_ряд) временного ряда:\n",
    "> Временной ряд – это последовательность значений, описывающих протекающий во времени процесс, измеренных в последовательные моменты времени, обычно через равные промежутки\n",
    "\n",
    "Таким образом, данные оказываются упорядочены относительно неслучайных моментов времени, и, значит, в отличие от случайных выборок, могут содержать в себе дополнительную информацию, которую мы постараемся извлечь. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Импортируем нужные библиотеки. В основном нам понадобится модуль  [statsmodels](http://statsmodels.sourceforge.net/stable/), в котором реализованы многочисленные методы статистического моделирования, в том числе для временных рядов. Для поклонников R, пересевших на питон, он может показаться очень родным, так как поддерживает написание формулировок моделей в стиле 'Wage ~ Age + Education'. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": []
   },
   "outputs": [],
   "source": [
    "import sys\n",
    "import warnings\n",
    "\n",
    "warnings.filterwarnings(\"ignore\")\n",
    "from itertools import product\n",
    "import matplotlib as mpl\n",
    "import matplotlib.dates as mdates\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import scipy.stats as scs\n",
    "import statsmodels.api as sm\n",
    "import statsmodels.formula.api as smf\n",
    "import statsmodels.tsa.api as smt\n",
    "from scipy.optimize import minimize\n",
    "from sklearn.metrics import mean_absolute_error, mean_squared_error\n",
    "from tqdm.notebook import tqdm\n",
    "\n",
    "%matplotlib inline\n",
    "\n",
    "\n",
    "from plotly import __version__\n",
    "from plotly import graph_objs as go\n",
    "from plotly.offline import download_plotlyjs, init_notebook_mode, iplot, plot\n",
    "\n",
    "init_notebook_mode(connected=True)\n",
    "\n",
    "\n",
    "def plotly_df(df, title=\"\"):\n",
    "    data = []\n",
    "\n",
    "    for column in df.columns:\n",
    "        trace = go.Scatter(x=df.index, y=df[column], mode=\"lines\", name=column)\n",
    "        data.append(trace)\n",
    "\n",
    "    layout = dict(title=title)\n",
    "    fig = dict(data=data, layout=layout)\n",
    "    iplot(fig, show_link=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Для примера возьмем реальные данные по часовому онлайну игроков в одной из мобильных игрушек"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dataset = pd.read_csv(\n",
    "    \"../../data/hour_online.csv\", index_col=[\"Time\"], parse_dates=[\"Time\"]\n",
    ")\n",
    "plotly_df(dataset, title=\"Online users\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Начнем моделирование с наивного предположения - \"завтра будет, как вчера\", но вместо модели вида $\\hat{y}_{t} = y_{t-1}$ будем считать, что будущее значение переменной зависит от среднего $n$ её предыдущих значений, а значит, воспользуемся скользящей средней. \n",
    "\n",
    "$\\hat{y}_{t} = \\frac{1}{k} \\displaystyle\\sum^{k-1}_{n=0} y_{t-n}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     0
    ]
   },
   "outputs": [],
   "source": [
    "def moving_average(series, n):\n",
    "    return np.average(series[-n:])\n",
    "\n",
    "\n",
    "moving_average(\n",
    "    dataset.Users, 24\n",
    ")  # посмотрим на прогноз, построенный по последнему наблюдаемому дню (24 часа)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "К сожалению, такой прогноз долгосрочным сделать не удастся, для получения предсказания на шаг вперед предыдущее значение должно быть фактически наблюдаемой величиной. Зато у скользящей средней есть другое применение - сглаживание исходного ряда для выявления трендов, в пандасе есть готовая реализация - [`DataFrame.rolling(window).mean()`](http://pandas.pydata.org/pandas-docs/stable/generated/pandas.DataFrame.rolling.html). Чем больше зададим ширину интервала - тем более сглаженным окажется тренд. В случае, если данные сильно зашумлены, что особенно часто встречается, например, в финансовых показателях, такая процедура может помочь увидеть общие паттерны."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     0
    ]
   },
   "outputs": [],
   "source": [
    "def plotMovingAverage(series, n, plot_bounds=False):\n",
    "\n",
    "    \"\"\"\n",
    "    series - dataframe with timeseries\n",
    "    n - rolling window size \n",
    "    plot_bounds: bool - whether to draw confidence interval\n",
    "    \"\"\"\n",
    "\n",
    "    rolling_mean = series.rolling(window=n).mean()\n",
    "\n",
    "    fig, ax = plt.subplots(figsize=(15, 5))\n",
    "    plt.title(\"Moving average\\n window size = {}\".format(n))\n",
    "    plt.plot(rolling_mean, \"g\", label=\"Rolling mean trend\")\n",
    "\n",
    "    # При желании, можно строить и доверительные интервалы для сглаженных значений\n",
    "    if plot_bounds:\n",
    "        rolling_std = series.rolling(window=n).std()\n",
    "        upper_bound = rolling_mean + 1.96 * rolling_std\n",
    "        lower_bound = rolling_mean - 1.96 * rolling_std\n",
    "        plt.plot(upper_bound, \"r--\", label=\"Upper Bound / Lower Bound\")\n",
    "        plt.plot(lower_bound, \"r--\")\n",
    "    plt.plot(series[n:], label=\"Actual values\")\n",
    "    plt.legend(loc=\"upper left\")\n",
    "    plt.grid(True)\n",
    "    # Деления соответствуют понедельникам что дает представление о недельной цикличности графика\n",
    "    ax.xaxis.set_major_locator(mdates.WeekdayLocator(byweekday=mdates.MONDAY))\n",
    "    # Отображать значение дат в формате yy-mm-dd\n",
    "    ax.xaxis.set_major_formatter(mdates.DateFormatter(\"%y-%m-%d\"))\n",
    "    plt.xticks(rotation=45)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plotMovingAverage(dataset, 24)  # сглаживаем по дням\n",
    "plotMovingAverage(dataset, 24 * 7, plot_bounds=True)  # сглаживаем по неделям"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Для нашего ряда тренды и так вполне очевидны, но если сгладить по дням, становится лучше видна динамика онлайна по будням и выходным (выходные - время поиграть), а недельное сглаживание хорошо отражает общие изменения, связанные с резким ростом числа активных игроков в феврале и последующим снижением в марте."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Модификацией простой скользящей средней является взвешенная средняя, внутри которой наблюдениям придаются различные веса, в сумме дающие единицу, при этом обычно последним наблюдениям присваивается больший вес. \n",
    "\n",
    "\n",
    "$\\hat{y}_{t} = \\displaystyle\\sum^{k}_{n=1} \\omega_n y_{t+1-n}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     0
    ]
   },
   "outputs": [],
   "source": [
    "def weighted_average(series, weights):\n",
    "    \"\"\"\n",
    "        Calculate weighted average on the series.\n",
    "        Assuming weights are sorted in descending order\n",
    "        (larger weights are assigned to more recent observations).\n",
    "    \"\"\"\n",
    "    result = 0.0\n",
    "    for n in range(len(weights)):\n",
    "        result += series.iloc[-n - 1] * weights[n]\n",
    "    return float(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "weighted_average(dataset.Users, [0.6, 0.2, 0.1, 0.07, 0.03])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Экспоненциальное сглаживание"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "А теперь посмотрим, что произойдёт, если вместо взвешивания последних $n$ значений ряда мы начнем взвешивать все доступные наблюдения, при этом экспоненциально уменьшая веса по мере углубления в исторические данные. В этом нам поможет формула простого [экспоненциального сглаживания](http://www.machinelearning.ru/wiki/index.php?title=Экспоненциальное_сглаживание):\n",
    "\n",
    "$$\\hat{y}_{t} = \\alpha \\cdot y_t + (1-\\alpha) \\cdot \\hat y_{t-1} $$\n",
    "\n",
    "Здесь модельное значение представляет собой средневзвешенную между текущим истинным и предыдущим модельным значениями. Вес $\\alpha$ называется сглаживающим фактором. Он определяет, как быстро мы будем \"забывать\" последнее доступное истинное наблюдение. Чем меньше $\\alpha$, тем больше влияния оказывают предыдущие модельные значения, и тем сильнее сглаживается ряд. \n",
    "\n",
    "Экспоненциальность скрывается в рекурсивности функции - каждый раз мы умножаем $(1-\\alpha)$ на предыдущее модельное значение, которое, в свою очередь, также содержало в себе $(1-\\alpha)$, и так до самого начала."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     0
    ]
   },
   "outputs": [],
   "source": [
    "def exponential_smoothing(series, alpha):\n",
    "    result = [series[0]]  # first value is same as series\n",
    "    for n in range(1, len(series)):\n",
    "        result.append(alpha * series[n] + (1 - alpha) * result[n - 1])\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     0
    ]
   },
   "outputs": [],
   "source": [
    "with plt.style.context(\"seaborn-white\"):\n",
    "    plt.figure(figsize=(20, 8))\n",
    "    for alpha in [0.3, 0.05]:\n",
    "        plt.plot(\n",
    "            exponential_smoothing(dataset.Users, alpha), label=\"Alpha {}\".format(alpha)\n",
    "        )\n",
    "    plt.plot(dataset.Users.values, \"c\", label=\"Actual\")\n",
    "    plt.legend(loc=\"best\")\n",
    "    plt.axis(\"tight\")\n",
    "    plt.title(\"Exponential Smoothing\")\n",
    "    plt.grid(True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Двойное экспоненциальное сглаживание"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "До сих пор мы могли получить от наших методов в лучшем случае прогноз лишь на одну точку вперёд (и ещё красиво сгладить ряд), это здорово, но недостаточно, поэтому переходим к расширению экспоненциального сглаживания, которое позволит строить прогноз сразу на две точки вперед (и тоже красиво сглаживать ряд).\n",
    "\n",
    "В этом нам поможет разбиение ряда на две составляющие - уровень (level, intercept) $\\ell$ и тренд $b$ (trend, slope). Уровень, или ожидаемое значение ряда, мы предсказывали при помощи предыдущих методов, а теперь такое же экспоненциальное сглаживание применим к тренду, наивно или не очень полагая, что будущее направление изменения ряда зависит от взвешенных предыдущих изменений.\n",
    "\n",
    "$$\\ell_x = \\alpha y_x + (1-\\alpha)(\\ell_{x-1} + b_{x-1})$$\n",
    "\n",
    "$$b_x = \\beta(\\ell_x - \\ell_{x-1}) + (1-\\beta)b_{x-1}$$\n",
    "\n",
    "$$\\hat{y}_{x+1} = \\ell_x + b_x$$\n",
    "\n",
    "В результате получаем набор функций. Первая описывает уровень - он, как и прежде, зависит от текущего значения ряда, а второе слагаемое теперь разбивается на предыдущее значение уровня и тренда. Вторая отвечает за тренд - он зависит от изменения уровня на текущем шаге, и от предыдущего значения тренда. Здесь в роли веса в экспоненциальном сглаживании выступает коэффициент $\\beta$. Наконец, итоговое предсказание представляет собой сумму модельных значений уровня и тренда."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     0,
     15
    ]
   },
   "outputs": [],
   "source": [
    "def double_exponential_smoothing(series, alpha, beta):\n",
    "    result = [series[0]]\n",
    "    for n in range(1, len(series) + 1):\n",
    "        if n == 1:\n",
    "            level, trend = series[0], series[1] - series[0]\n",
    "        if n >= len(series):  # прогнозируем\n",
    "            value = result[-1]\n",
    "        else:\n",
    "            value = series[n]\n",
    "        last_level, level = level, alpha * value + (1 - alpha) * (level + trend)\n",
    "        trend = beta * (level - last_level) + (1 - beta) * trend\n",
    "        result.append(level + trend)\n",
    "    return result\n",
    "\n",
    "\n",
    "with plt.style.context(\"seaborn-white\"):\n",
    "    plt.figure(figsize=(20, 8))\n",
    "    for alpha in [0.9, 0.02]:\n",
    "        for beta in [0.9, 0.02]:\n",
    "            plt.plot(\n",
    "                double_exponential_smoothing(dataset.Users, alpha, beta),\n",
    "                label=\"Alpha {}, beta {}\".format(alpha, beta),\n",
    "            )\n",
    "    plt.plot(dataset.Users.values, label=\"Actual\")\n",
    "    plt.legend(loc=\"best\")\n",
    "    plt.axis(\"tight\")\n",
    "    plt.title(\"Double Exponential Smoothing\")\n",
    "    plt.grid(True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Теперь настраивать пришлось уже два параметра - $\\alpha$ и $\\beta$. Первый отвечает за сглаживание ряда вокруг тренда, второй - за сглаживание самого тренда. Чем выше значения, тем больший вес будет отдаваться последним наблюдениям и тем менее сглаженным окажется модельный ряд. Комбинации параметров могут выдавать достаточно причудливые результаты, особенно если задавать их руками. А о не ручном подборе параметров расскажу чуть ниже, сразу после тройного экспоненциального сглаживания."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Тройное экспоненциальное сглаживание a.k.a. Holt-Winters\n",
    "\n",
    "Итак, успешно добрались до следующего варианта экспоненциального сглаживания, на сей раз тройного.\n",
    "\n",
    "Идея этого метода заключается в добавлении еще одной, третьей, компоненты - сезонности. Соответственно, метод применим только в случае, если ряд этой сезонностью не обделён, что в нашем случае верно. Сезонная компонента в модели будет объяснять повторяющиеся колебания вокруг уровня и тренда, а характеризоваться она будет длиной сезона - периодом, после которого начинаются повторения колебаний. Для каждого наблюдения в сезоне формируется своя компонента, например, если длина сезона составляет 7 (например, недельная сезонность), то получим 7 сезонных компонент, по штуке на каждый из дней недели.\n",
    "\n",
    "Получаем новую систему:\n",
    "\n",
    "$$\\ell_x = \\alpha(y_x - s_{x-L}) + (1-\\alpha)(\\ell_{x-1} + b_{x-1})$$\n",
    "\n",
    "$$b_x = \\beta(\\ell_x - \\ell_{x-1}) + (1-\\beta)b_{x-1}$$\n",
    "\n",
    "$$s_x = \\gamma(y_x - \\ell_x) + (1-\\gamma)s_{x-L}$$\n",
    "\n",
    "$$\\hat{y}_{x+m} = \\ell_x + mb_x + s_{x-L+1+(m-1)modL}$$\n",
    "\n",
    "Уровень теперь зависит от текущего значения ряда за вычетом соответствующей сезонной компоненты, тренд остаётся без изменений, а сезонная компонента зависит от текущего значения ряда за вычетом уровня и от предыдущего значения компоненты. При этом компоненты сглаживаются через все доступные сезоны, например, если это компонента, отвечающая за понедельник, от и усредняться она будет только с другими понедельниками. Подробнее про работу усреднений и оценку начальных значений тренда и сезонных компонент можно почитать [здесь](http://www.itl.nist.gov/div898/handbook/pmc/section4/pmc435.htm). Теперь, имея сезонную компоненту, мы можем предсказывать уже не на один, и даже не на два, а на произвольные $m$ шагов вперёд, что не может не радовать. \n",
    "\n",
    "Ниже приведен код для построения модели тройного экспоненциального сглаживания, также известного по фамилиям её создателей - Чарльза Хольта и его студента Питера Винтерса. \n",
    "Дополнительно в модель включен метод Брутлага для построения доверительных интервалов:\n",
    "\n",
    "$$\\hat y_{max_x}=\\ell_{x−1}+b_{x−1}+s_{x−T}+m⋅d_{t−T}$$\n",
    "\n",
    "$$\\hat y_{min_x}=\\ell_{x−1}+b_{x−1}+s_{x−T}-m⋅d_{t−T}$$\n",
    "\n",
    "$$d_t=\\gamma∣y_t−\\hat y_t∣+(1−\\gamma)d_{t−T},$$\n",
    "\n",
    "где $T$ - длина сезона, $d$ - предсказанное отклонение, а остальные параметры берутся из тройного сглаживани. Подробнее о методе и о его применении к поиску аномалий во временных рядах можно прочесть [здесь](https://fedcsis.org/proceedings/2012/pliks/118.pdf)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     0
    ]
   },
   "outputs": [],
   "source": [
    "class HoltWinters:\n",
    "\n",
    "    \"\"\"\n",
    "    Модель Хольта-Винтерса с методом Брутлага для детектирования аномалий\n",
    "    https://fedcsis.org/proceedings/2012/pliks/118.pdf\n",
    "    \n",
    "    \n",
    "    # series - исходный временной ряд\n",
    "    # slen - длина сезона\n",
    "    # alpha, beta, gamma - коэффициенты модели Хольта-Винтерса\n",
    "    # n_preds - горизонт предсказаний\n",
    "    # scaling_factor - задаёт ширину доверительного интервала по Брутлагу (обычно принимает значения от 2 до 3)\n",
    "    \n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self, series, slen, alpha, beta, gamma, n_preds, scaling_factor=1.96):\n",
    "        self.series = series\n",
    "        self.slen = slen\n",
    "        self.alpha = alpha\n",
    "        self.beta = beta\n",
    "        self.gamma = gamma\n",
    "        self.n_preds = n_preds\n",
    "        self.scaling_factor = scaling_factor\n",
    "\n",
    "    def initial_trend(self):\n",
    "        sum = 0.0\n",
    "        for i in range(self.slen):\n",
    "            sum += float(self.series[i + self.slen] - self.series[i]) / self.slen\n",
    "        return sum / self.slen\n",
    "\n",
    "    def initial_seasonal_components(self):\n",
    "        seasonals = {}\n",
    "        season_averages = []\n",
    "        n_seasons = int(len(self.series) / self.slen)\n",
    "        # вычисляем сезонные средние\n",
    "        for j in range(n_seasons):\n",
    "            season_averages.append(\n",
    "                sum(self.series[self.slen * j : self.slen * j + self.slen])\n",
    "                / float(self.slen)\n",
    "            )\n",
    "        # вычисляем начальные значения\n",
    "        for i in range(self.slen):\n",
    "            sum_of_vals_over_avg = 0.0\n",
    "            for j in range(n_seasons):\n",
    "                sum_of_vals_over_avg += (\n",
    "                    self.series[self.slen * j + i] - season_averages[j]\n",
    "                )\n",
    "            seasonals[i] = sum_of_vals_over_avg / n_seasons\n",
    "        return seasonals\n",
    "\n",
    "    def triple_exponential_smoothing(self):\n",
    "        self.result = []\n",
    "        self.Smooth = []\n",
    "        self.Season = []\n",
    "        self.Trend = []\n",
    "        self.PredictedDeviation = []\n",
    "        self.UpperBond = []\n",
    "        self.LowerBond = []\n",
    "\n",
    "        seasonals = self.initial_seasonal_components()\n",
    "\n",
    "        for i in range(len(self.series) + self.n_preds):\n",
    "            if i == 0:  # инициализируем значения компонент\n",
    "                smooth = self.series[0]\n",
    "                trend = self.initial_trend()\n",
    "                self.result.append(self.series[0])\n",
    "                self.Smooth.append(smooth)\n",
    "                self.Trend.append(trend)\n",
    "                self.Season.append(seasonals[i % self.slen])\n",
    "\n",
    "                self.PredictedDeviation.append(0)\n",
    "\n",
    "                self.UpperBond.append(\n",
    "                    self.result[0] + self.scaling_factor * self.PredictedDeviation[0]\n",
    "                )\n",
    "\n",
    "                self.LowerBond.append(\n",
    "                    self.result[0] - self.scaling_factor * self.PredictedDeviation[0]\n",
    "                )\n",
    "\n",
    "                continue\n",
    "            if i >= len(self.series):  # прогнозируем\n",
    "                m = i - len(self.series) + 1\n",
    "                self.result.append((smooth + m * trend) + seasonals[i % self.slen])\n",
    "\n",
    "                # во время прогноза с каждым шагом увеличиваем неопределенность\n",
    "                self.PredictedDeviation.append(self.PredictedDeviation[-1] * 1.01)\n",
    "\n",
    "            else:\n",
    "                val = self.series[i]\n",
    "                last_smooth, smooth = (\n",
    "                    smooth,\n",
    "                    self.alpha * (val - seasonals[i % self.slen])\n",
    "                    + (1 - self.alpha) * (smooth + trend),\n",
    "                )\n",
    "                trend = self.beta * (smooth - last_smooth) + (1 - self.beta) * trend\n",
    "                seasonals[i % self.slen] = (\n",
    "                    self.gamma * (val - smooth)\n",
    "                    + (1 - self.gamma) * seasonals[i % self.slen]\n",
    "                )\n",
    "                self.result.append(smooth + trend + seasonals[i % self.slen])\n",
    "\n",
    "                # Отклонение рассчитывается в соответствии с алгоритмом Брутлага\n",
    "                self.PredictedDeviation.append(\n",
    "                    self.gamma * np.abs(self.series[i] - self.result[i])\n",
    "                    + (1 - self.gamma) * self.PredictedDeviation[-1]\n",
    "                )\n",
    "\n",
    "            self.UpperBond.append(\n",
    "                self.result[-1] + self.scaling_factor * self.PredictedDeviation[-1]\n",
    "            )\n",
    "\n",
    "            self.LowerBond.append(\n",
    "                self.result[-1] - self.scaling_factor * self.PredictedDeviation[-1]\n",
    "            )\n",
    "\n",
    "            self.Smooth.append(smooth)\n",
    "            self.Trend.append(trend)\n",
    "            self.Season.append(seasonals[i % self.slen])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Кросс-валидация на временных рядах\n",
    "\n",
    "Перед тем, как построить модель, поговорим, наконец, о не ручной оценке параметров для моделей. \n",
    "\n",
    "Ничего необычного здесь нет, по-прежнему сначала необходимо выбрать подходящуюю для данной задачи функцию потерь: [RMSE](https://en.wikipedia.org/wiki/Root-mean-square_deviation), [MAE](https://en.wikipedia.org/wiki/Mean_absolute_error), [MAPE](https://en.wikipedia.org/wiki/Mean_absolute_percentage_error) и др., которая будет следить за качеством подгонки модели под исходные данные. Затем будем оценивать на кросс-валидации значение функции потерь при данных параметрах модели, искать градиент, менять в соответствии с ним параметры и бодро опускаться в сторону глобального минимума ошибки. \n",
    "\n",
    "Небольшая загвоздка возникает только в кросс-валидации. Проблема состоит в том, что временной ряд имеет, как ни парадоксально, временную структуру, и случайно перемешивать в фолдах значения всего ряда без сохранения этой структуры нельзя, иначе в процессе потеряются все взаимосвязи наблюдений друг с другом. Поэтому придется использовать чуть более хитрый способ для оптимизации параметров, официального названия которому я так и не нашел, но на сайте [CrossValidated](https://stats.stackexchange.com/questions/14099/using-k-fold-cross-validation-for-time-series-model-selection), где можно найти ответы на всё, кроме главного вопроса Жизни, Вселенной и Всего Остального, предлагают название \"cross-validation on a rolling basis\", что не дословно можно перевести как кросс-валидация на скользящем окне.\n",
    "\n",
    "Суть достаточно проста - начинаем обучать модель на небольшом отрезке временного ряда, от начала до некоторого $t$, делаем прогноз на $t+n$ шагов вперед и считаем ошибку. Далее расширяем обучающую выборку до $t+n$ значения и прогнозируем с $t+n$ до $t+2*n$, так продолжаем двигать тестовый отрезок ряда до тех пор, пока не упрёмся в последнее доступное наблюдение. В итоге получим столько фолдов, сколько $n$ уместится в промежуток между изначальным обучающим отрезком и всей длиной ряда.\n",
    "\n",
    "<img src=\"https://habrastorage.org/files/f5c/7cd/b39/f5c7cdb39ccd4ba68378ca232d20d864.png\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Код для кросс-валидации на временном ряду. Значение длины сезона 24\\*7 возникло не случайно - в исходном ряде отчетливо видна дневная сезонность, (отсюда 24), и недельная - по будням ниже, на выходных - выше, (отсюда 7), суммарно сезонных компонент получится 24\\*7."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.model_selection import TimeSeriesSplit\n",
    "\n",
    "\n",
    "def timeseriesCVscore(x):\n",
    "    # вектор ошибок\n",
    "    errors = []\n",
    "\n",
    "    values = data.values\n",
    "    alpha, beta, gamma = x\n",
    "\n",
    "    # задаём число фолдов для кросс-валидации\n",
    "    tscv = TimeSeriesSplit(n_splits=3)\n",
    "\n",
    "    # идем по фолдам, на каждом обучаем модель, строим прогноз на отложенной выборке и считаем ошибку\n",
    "    for train, test in tscv.split(values):\n",
    "\n",
    "        model = HoltWinters(\n",
    "            series=values[train],\n",
    "            slen=24 * 7,\n",
    "            alpha=alpha,\n",
    "            beta=beta,\n",
    "            gamma=gamma,\n",
    "            n_preds=len(test),\n",
    "        )\n",
    "        model.triple_exponential_smoothing()\n",
    "\n",
    "        predictions = model.result[-len(test) :]\n",
    "        actual = values[test]\n",
    "        error = mean_squared_error(predictions, actual)\n",
    "        errors.append(error)\n",
    "    return np.mean(np.array(errors))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В модели Хольта-Винтерса, как и в остальных моделях экспоненциального сглаживания, есть ограничение на величину сглаживающих параметров - каждый из них может принимать значения от 0 до 1, поэтому для минимизации функции потерь нужно выбирать алгоритм, поддерживающий ограничения на параметры, в данном случае - Truncated Newton conjugate gradient."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "data = dataset.Users[:-500]  # отложим часть данных для тестирования\n",
    "\n",
    "# инициализируем значения параметров\n",
    "x = [0, 0, 0]\n",
    "\n",
    "# Минимизируем функцию потерь с ограничениями на параметры\n",
    "opt = minimize(timeseriesCVscore, x0=x, method=\"TNC\", bounds=((0, 1), (0, 1), (0, 1)))\n",
    "\n",
    "# Из оптимизатора берем оптимальное значение параметров\n",
    "alpha_final, beta_final, gamma_final = opt.x\n",
    "print(alpha_final, beta_final, gamma_final)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Передадим полученные оптимальные значения коэффициентов $\\alpha$, $\\beta$ и $\\gamma$ и построим прогноз на 5 дней вперёд (128 часов)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Передаем оптимальные значения модели,\n",
    "data = dataset.Users\n",
    "model = HoltWinters(\n",
    "    data[:-128],\n",
    "    slen=24 * 7,\n",
    "    alpha=alpha_final,\n",
    "    beta=beta_final,\n",
    "    gamma=gamma_final,\n",
    "    n_preds=128,\n",
    "    scaling_factor=2.56,\n",
    ")\n",
    "model.triple_exponential_smoothing()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Код для отрисовки графика"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     0
    ]
   },
   "outputs": [],
   "source": [
    "def plotHoltWinters():\n",
    "    Anomalies = np.array([np.NaN] * len(data))\n",
    "    Anomalies[data.values < model.LowerBond] = data.values[\n",
    "        data.values < model.LowerBond\n",
    "    ]\n",
    "    plt.figure(figsize=(25, 10))\n",
    "    plt.plot(model.result, label=\"Model\")\n",
    "    plt.plot(model.UpperBond, \"r--\", alpha=0.5, label=\"Up/Low confidence\")\n",
    "    plt.plot(model.LowerBond, \"r--\", alpha=0.5)\n",
    "    plt.fill_between(\n",
    "        x=range(0, len(model.result)),\n",
    "        y1=model.UpperBond,\n",
    "        y2=model.LowerBond,\n",
    "        alpha=0.5,\n",
    "        color=\"grey\",\n",
    "    )\n",
    "    plt.plot(data.values, label=\"Actual\")\n",
    "    plt.plot(Anomalies, \"o\", markersize=10, label=\"Anomalies\")\n",
    "    plt.axvspan(len(data) - 128, len(data), alpha=0.5, color=\"lightgrey\")\n",
    "    plt.grid(True)\n",
    "    plt.axis(\"tight\")\n",
    "    plt.legend(loc=\"best\", fontsize=13);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plotHoltWinters()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Судя по графику, модель неплохо описала исходный временной ряд, уловив недельную и дневную сезонность, и даже смогла поймать аномальные снижения, вышедшие за пределы доверительных интервалов. Если посмотреть на смоделированное отклонение, хорошо видно, что модель достаточно резко регирует на значительные изменения в структуре ряда, но при этом быстро возвращает дисперсию к обычным значениям, \"забывая\" прошлое. Такая особенность позволяет неплохо и без значительных затрат на подготовку-обучение модели настроить систему по детектированию аномалий даже в достаточно шумных рядах."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.figure(figsize=(25, 5))\n",
    "plt.plot(model.PredictedDeviation)\n",
    "plt.grid(True)\n",
    "plt.axis(\"tight\")\n",
    "plt.title(\"Brutlag's predicted deviation\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Эконометрический подход"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Стационарность\n",
    "\n",
    "Перед тем, как перейти к моделированию, стоит сказать о таком важном свойстве временного ряда, как [**стационарность**](https://ru.wikipedia.org/wiki/Стационарность). \n",
    "Под стационарностью понимают свойство процесса не менять своих статистических характеристик с течением времени, а именно постоянство матожидания, постоянство дисперсии (она же [гомоскедастичность](https://ru.wikipedia.org/wiki/Гомоскедастичность)) и независимость ковариационной функции от времени (должна зависеть только от расстояния между наблюдениями). Наглядно можно посмотреть на эти свойства на картинках, взятых из поста [Sean Abu](http://www.seanabu.com/2016/03/22/time-series-seasonal-ARIMA-model-in-python/):\n",
    "\n",
    "- Временной ряд справа не является стационарным, так как его матожидание со временем растёт\n",
    "\n",
    "<img src=\"https://habrastorage.org/files/20c/9d8/a63/20c9d8a633ec436f91dccd4aedcc6940.png\"/>\n",
    "\n",
    "- Здесь не повезло с дисперсией - разброс значений ряда существенно варьируется в зависимости от периода\n",
    "\n",
    "<img src=\"https://habrastorage.org/files/b88/eec/a67/b88eeca676d642449cab135273fd5a95.png\"/>\n",
    "\n",
    "- Наконец, на последнем графике видно, что значения ряда внезапно становятся ближе друг ко другу, образуя некоторый кластер, а в результате получаем непостоянство ковариаций\n",
    "\n",
    "<img src=\"https://habrastorage.org/files/2f6/1ee/cb2/2f61eecb20714352840748b826e38680.png\"/>\n",
    "\n",
    "Почему стационарность так важна? По стационарному ряду просто строить прогноз, так как мы полагаем, что его будущие статистические характеристики не будут отличаться от наблюдаемых текущих. Большинство моделей временных рядов так или иначе моделируют и предсказывают эти характеристики (например, матожидание или дисперсию), поэтому в случае нестационарности исходного ряда предсказания окажутся неверными. К сожалению, большинство временных рядов, с которыми приходится сталкиваться за пределами учебных материалов, стационарными не являются, но с этим можно (и нужно) бороться.\n",
    "\n",
    "Чтобы бороться с нестационарностью, нужно узнать её в лицо, потому посмотрим, как её детектировать. Для этого обратимся к белому шуму и случайному блужданию, чтобы выяснить как попасть из одного в другое бесплатно и без смс."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "График белого шума:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "white_noise = np.random.normal(size=1000)\n",
    "with plt.style.context(\"bmh\"):\n",
    "    plt.figure(figsize=(15, 5))\n",
    "    plt.plot(white_noise)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Итак, процесс, порожденный стандартным нормальным распределением, стационарен, колеблется вокруг нуля с отклонением в 1. Теперь на его основе сгенерируем новый процесс, в котором каждое последующее значение будет зависеть от предыдущего: $x_t = \\rho x_{t-1} + e_t$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Код для отрисовки графиков"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     0
    ]
   },
   "outputs": [],
   "source": [
    "def plotProcess(n_samples=1000, rho=0):\n",
    "    x = w = np.random.normal(size=n_samples)\n",
    "    for t in range(n_samples):\n",
    "        x[t] = rho * x[t - 1] + w[t]\n",
    "\n",
    "    with plt.style.context(\"bmh\"):\n",
    "        plt.figure(figsize=(10, 3))\n",
    "        plt.plot(x)\n",
    "        plt.title(\n",
    "            \"Rho {}\\n Dickey-Fuller p-value: {}\".format(\n",
    "                rho, round(sm.tsa.stattools.adfuller(x)[1], 3)\n",
    "            )\n",
    "        )\n",
    "\n",
    "\n",
    "for rho in [0, 0.6, 0.9, 1]:\n",
    "    plotProcess(rho=rho)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "На первом графике получился точно такой же стационарный белый шум, который строился раньше. На втором значение $\\rho$ увеличилось до 0.6, в результате чего на графике стали появляться более широкие циклы, но в целом стационарным он быть пока не перестал. Третий график всё сильнее отклоняется от нулевого среднего значения, но всё ещё колеблется вокруг него. Наконец, значение $\\rho$ равное единице дало процесс случайного блуждания - ряд не стационарен.\n",
    "\n",
    "Происходит это из-за того, что при достижении критической единицы, ряд $x_t = \\rho x_{t-1} + e_t$ перестаёт возвращаться к своему среднему значению. Если вычесть из левой и правой части $x_{t-1}$, то получим $x_t - x_{t-1} = (\\rho - 1) x_{t-1} + e_t$, где выражение слева - первые разности. Если $\\rho=1$, то первые разности дадут стационарный белый шум $e_t$. Этот факт лёг в основу теста [Дики-Фуллера](https://ru.wikipedia.org/wiki/Тест_Дики_—_Фуллера) на стационарность ряда (наличие единичного корня). Если из нестационарного ряда первыми разностями удаётся получить стационарный, то он называется интегрированным первого порядка.\n",
    "Нулевая гипотеза - ряд не стационарен, отвергалась на первых трех графиках, и принялась на последнем. Стоит сказать, что не всегда для получения стационарного ряда хватает первых разностей, так как процесс может быть интегрированным с более высоким порядком (иметь несколько единичных корней), для проверки таких случаев используют расширенный тест Дики-Фуллера, проверяющий сразу несколько лагов.\n",
    "\n",
    "Бороться с нестационарностью можно множеством способов - разностями различного порядка, выделением тренда и сезонности, сглаживаниями и преобразованиями, например, Бокса-Кокса или логарифмированием."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Избавляемся от нестационарности и строим SARIMA"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "code_folding": []
   },
   "source": [
    "Попробуем теперь построить ARIMA модель для онлайна игроков, пройдя все ~~круги ада~~ стадии приведения ряда к стационарному виду. Про саму модель уже не раз писали на хабре - [Построение модели SARIMA с помощью Python+R](https://habrahabr.ru/post/210530/), [Анализ временных рядов с помощью python](https://habrahabr.ru/post/207160/), поэтому подробно останавливаться на ней не буду."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Код для отрисовки графиков"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     0
    ]
   },
   "outputs": [],
   "source": [
    "def tsplot(y, lags=None, figsize=(12, 7), style=\"bmh\"):\n",
    "    \"\"\"\n",
    "        Plot time series, its ACF and PACF, calculate Dickey–Fuller test\n",
    "        \n",
    "        y - timeseries\n",
    "        lags - how many lags to include in ACF, PACF calculation\n",
    "    \"\"\"\n",
    "    if not isinstance(y, pd.Series):\n",
    "        y = pd.Series(y)\n",
    "\n",
    "    with plt.style.context(style):\n",
    "        fig = plt.figure(figsize=figsize)\n",
    "        layout = (2, 2)\n",
    "        ts_ax = plt.subplot2grid(layout, (0, 0), colspan=2)\n",
    "        acf_ax = plt.subplot2grid(layout, (1, 0))\n",
    "        pacf_ax = plt.subplot2grid(layout, (1, 1))\n",
    "\n",
    "        ts_ax.plot(y)\n",
    "        p_value = sm.tsa.stattools.adfuller(y)[1]\n",
    "        ts_ax.set_title(\n",
    "            \"Time Series Analysis Plots\\n Dickey-Fuller: p={0:.5f}\".format(p_value)\n",
    "        )\n",
    "        smt.graphics.plot_acf(y, lags=lags, ax=acf_ax)\n",
    "        smt.graphics.plot_pacf(y, lags=lags, ax=pacf_ax)\n",
    "        plt.tight_layout()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tsplot(dataset.Users, lags=30)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Как и следовало ожидать, исходный ряд стационарным не является, критерий Дики-Фуллера не отверг нулевую гипотезу о наличии единичного корня. Попробуем стабилизировать дисперсию преоразованием Бокса-Кокса"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     0
    ]
   },
   "outputs": [],
   "source": [
    "def invboxcox(y, lmbda):\n",
    "    # обратное преобразование Бокса-Кокса\n",
    "    if lmbda == 0:\n",
    "        return np.exp(y)\n",
    "    else:\n",
    "        return np.exp(np.log(lmbda * y + 1) / lmbda)\n",
    "\n",
    "\n",
    "data = dataset.copy()\n",
    "data[\"Users_box\"], lmbda = scs.boxcox(\n",
    "    data.Users + 1\n",
    ")  # прибавляем единицу, так как в исходном ряде есть нули\n",
    "tsplot(data.Users_box, lags=30)\n",
    "print(\"Оптимальный параметр преобразования Бокса-Кокса: %f\" % lmbda)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Уже лучше, однако критерий Дики-Фуллера по-прежнему не отвергает гипотезу о нестационарности ряда. А автокорреляционная функция явно намекает на сезонность в получившемся ряде. Возьмём сезонные разности:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "data[\"Users_box_season\"] = data.Users_box - data.Users_box.shift(24 * 7)\n",
    "tsplot(data.Users_box_season[24 * 7 :], lags=30)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Критерий Дики-Фуллера теперь отвергает нулевую гипотезу о нестационарности, но автокорреляционная функция всё ещё выглядит нехорошо из-за большого числа значимых лагов. Так как на графике частной автокорреляционной функции значим лишь один лаг, стоит взять еще первые разности, чтобы привести, наконец, ряд к стационарному виду."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "data[\"Users_box_season_diff\"] = data.Users_box_season - data.Users_box_season.shift(1)\n",
    "tsplot(data.Users_box_season_diff[24 * 7 + 1 :], lags=30)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Наконец, получили стационарный ряд, по автокорреляционной и частной автокорреляционной функции прикинем параметры для SARIMA модели, на забыв, что предварительно уже сделали первые и сезонные разности."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Начальные приближения Q = 1, P = 4, q = 3, p = 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# setting initial values and some bounds for them\n",
    "ps = range(2, 5)\n",
    "d = 1\n",
    "qs = range(2, 5)\n",
    "Ps = range(0, 2)\n",
    "D = 1\n",
    "Qs = range(0, 2)\n",
    "s = 24  # season length is still 24\n",
    "\n",
    "# creating list with all the possible combinations of parameters\n",
    "parameters = product(ps, qs, Ps, Qs)\n",
    "parameters_list = list(parameters)\n",
    "len(parameters_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def optimizeSARIMA(series, parameters_list, d, D, s):\n",
    "    \"\"\"\n",
    "        Return dataframe with parameters and corresponding AIC\n",
    "        \n",
    "        series – the time series\n",
    "        parameters_list - list with (p, q, P, Q) tuples\n",
    "        d - integration order in ARIMA model\n",
    "        D - seasonal integration order \n",
    "        s - length of season\n",
    "    \"\"\"\n",
    "\n",
    "    results = []\n",
    "    best_aic = float(\"inf\")\n",
    "\n",
    "    for param in tqdm(parameters_list):\n",
    "        # we need try-except because on some combinations model fails to converge\n",
    "        try:\n",
    "            model = sm.tsa.statespace.SARIMAX(\n",
    "                series,\n",
    "                order=(param[0], d, param[1]),\n",
    "                seasonal_order=(param[2], D, param[3], s),\n",
    "            ).fit(disp=-1)\n",
    "        except:\n",
    "            continue\n",
    "        aic = model.aic\n",
    "        # saving best model, AIC and parameters\n",
    "        if aic < best_aic:\n",
    "            best_model = model\n",
    "            best_aic = aic\n",
    "            best_param = param\n",
    "        results.append([param, model.aic])\n",
    "\n",
    "    result_table = pd.DataFrame(results)\n",
    "    result_table.columns = [\"parameters\", \"aic\"]\n",
    "    # sorting in ascending order, the lower AIC is - the better\n",
    "    result_table = result_table.sort_values(by=\"aic\", ascending=True).reset_index(\n",
    "        drop=True\n",
    "    )\n",
    "\n",
    "    return result_table"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "result_table = optimizeSARIMA(data.Users_box_season, parameters_list, d, D, s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Лучшие параметры загоняем в модель:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# set the parameters that give the lowest AIC\n",
    "p, q, P, Q = result_table.parameters[0]\n",
    "\n",
    "best_model = sm.tsa.statespace.SARIMAX(\n",
    "    ads.Ads, order=(p, d, q), seasonal_order=(P, D, Q, s)\n",
    ").fit(disp=-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(best_model.summary())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Проверим остатки модели:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tsplot(best_model.resid[24:], lags=30)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Что ж, остатки стационарны, явных автокорреляций нет, построим прогноз по получившейся модели"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "data[\"arima_model\"] = invboxcox(best_model.fittedvalues, lmbda)\n",
    "forecast = invboxcox(\n",
    "    best_model.predict(start=data.shape[0], end=data.shape[0] + 100), lmbda\n",
    ")\n",
    "forecast = data.arima_model.append(forecast).values[-500:]\n",
    "actual = data.Users.values[-400:]\n",
    "plt.figure(figsize=(15, 7))\n",
    "plt.plot(forecast, color=\"r\", label=\"model\")\n",
    "plt.title(\n",
    "    \"SARIMA model\\n Mean absolute error {} users\".format(\n",
    "        round(mean_absolute_error(data.dropna().Users, data.dropna().arima_model))\n",
    "    )\n",
    ")\n",
    "plt.plot(actual, label=\"actual\")\n",
    "plt.legend()\n",
    "plt.axvspan(len(actual), len(forecast), alpha=0.5, color=\"lightgrey\")\n",
    "plt.grid(True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В финале получаем достаточно адекватный прогноз, в среднем модель ошибалась на 1.3 K пользователей, что очень и очень неплохо, однако суммарные затраты на подготовку данных, приведение к стационарности, определение и перебор параметров могут такой точности и не стоить."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Линейные и не очень модели на временных рядах\n",
    "\n",
    "Снова небольшое лирическое отступление. Часто на работе приходится строить модели, руководствуясь одним основополагающим принципом – [*быстро, качественно, недорого*](http://lurkmore.to/Быстро,_качественно,_недорого). Поэтому часть моделей могут банально не подойти для \"продакшн-решений\", так как либо требуют слишком больших затрат по подготовке данных (например, SARIMA), либо сложно настраиваются (хороший пример – SARIMA), либо требуют частого переобучения на новых данных (опять SARIMA), поэтому зачастую гораздо проще бывает выделить несколько признаков из имеющегося временного ряда и построить по ним обычную линейную регрессию или навесить решаюший лес. Дешево и сердито.\n",
    "\n",
    "Возможно, этот подход не является значительно подкрепленным теорией, нарушает различные предпосылки, например, условия Гаусса-Маркова, особенно пункт про некоррелированность ошибок, однако на практике нередко выручает и достаточно активно используется в соревнованиях по машинному обучению."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Извлечение признаков (Feature exctraction)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Помимо стандартных признаков вроде лагов целевой переменной, много информации содержат в себе дата и время. Про извлечение признаков из них уже здорово описано в одной из [предыдущих статей](https://habrahabr.ru/company/ods/blog/325422/#vremennye-ryady-veb-i-prochee) курса.\n",
    "\n",
    "Добавлю только про еще один вариант кодирования категориальных признаков – кодирование средним. Если не хочется раздувать датасет множеством дамми-переменных, которые могут привести к потере информации о расстоянии, а в вещественном виде возникают противоречивые результаты а-ля \"0 часов < 23 часа\", то можно закодировать переменную чуть более интерпретируемыми значениями. Естественный вариант – закодировать средним значением целевой переменной. В нашем случае каждый день недели или час дня можно закодировать сооветствующим средним числом игроков, находившихся в этот день недели или час онлайн. При этом важно следить за тем, чтобы расчет среднего значения производился только в рамках тренировочного датасета (или в рамках текущего наблюдаемого фолда при кросс-валидации), иначе можно ненароком привнести в модель информацию о будущем."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def code_mean(data, cat_feature, real_feature):\n",
    "    \"\"\"\n",
    "    Возвращает словарь, где ключами являются уникальные категории признака cat_feature, \n",
    "    а значениями - средние по real_feature\n",
    "    \"\"\"\n",
    "    return dict(data.groupby(cat_feature)[real_feature].mean())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Создадим новый датафрейм и добавим в него час, день недели и выходной в качестве категориальных переменных. Для этого переводим имеющийся в датафрейме индекс в формат `datetime`, и извлекаем из него `hour` и `weekday`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = pd.DataFrame(dataset.copy())\n",
    "data.columns = [\"y\"]\n",
    "\n",
    "data.index = data.index.to_datetime()\n",
    "data[\"hour\"] = data.index.hour\n",
    "data[\"weekday\"] = data.index.weekday\n",
    "data[\"is_weekend\"] = data.weekday.isin([5, 6]) * 1\n",
    "data.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Посмотрим на средние по дням недели"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "code_mean(data, \"weekday\", \"y\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Помимо перечисленных преобразований для увеличения числа признаков используют и множество других метрик, например, максимальное/минимальное значение, наблюдавшееся в скользящем по ряду окне, медианы, число пиков, взвешенные дисперсии и многое другое. Автоматически этим занимается уже упоминавшаяся в курсе [библиотека tsfresh](https://github.com/blue-yonder/tsfresh)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Для удобства все преобразования можно записать в одну функцию, которая сразу же будет возвращать разбитые на трейн и тест датасеты и целевые переменные."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     0
    ]
   },
   "outputs": [],
   "source": [
    "def prepareData(data, lag_start=5, lag_end=20, test_size=0.15):\n",
    "\n",
    "    data = pd.DataFrame(data.copy())\n",
    "    data.columns = [\"y\"]\n",
    "\n",
    "    # считаем индекс в датафрейме, после которого начинается тестовый отрезок\n",
    "    test_index = int(len(data) * (1 - test_size))\n",
    "\n",
    "    # добавляем лаги исходного ряда в качестве признаков\n",
    "    for i in range(lag_start, lag_end):\n",
    "        data[\"lag_{}\".format(i)] = data.y.shift(i)\n",
    "\n",
    "    data.index = data.index.to_datetime()\n",
    "    data[\"hour\"] = data.index.hour\n",
    "    data[\"weekday\"] = data.index.weekday\n",
    "    data[\"is_weekend\"] = data.weekday.isin([5, 6]) * 1\n",
    "\n",
    "    # считаем средние только по тренировочной части, чтобы избежать лика\n",
    "    data[\"weekday_average\"] = list(\n",
    "        map(code_mean(data[:test_index], \"weekday\", \"y\").get, data.weekday)\n",
    "    )\n",
    "    data[\"hour_average\"] = list(\n",
    "        map(code_mean(data[:test_index], \"hour\", \"y\").get, data.hour)\n",
    "    )\n",
    "\n",
    "    # выкидываем закодированные средними признаки\n",
    "    data.drop([\"hour\", \"weekday\"], axis=1, inplace=True)\n",
    "\n",
    "    data = data.dropna()\n",
    "    data = data.reset_index(drop=True)\n",
    "\n",
    "    # разбиваем весь датасет на тренировочную и тестовую выборку\n",
    "    X_train = data.loc[:test_index].drop([\"y\"], axis=1)\n",
    "    y_train = data.loc[:test_index][\"y\"]\n",
    "    X_test = data.loc[test_index:].drop([\"y\"], axis=1)\n",
    "    y_test = data.loc[test_index:][\"y\"]\n",
    "\n",
    "    return X_train, X_test, y_train, y_test"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Обучим на получившихся данных простую линейную регрессию. При этом лаги будем брать начиная с двенадцатого, таким образом модель будет способна строить предсказания на 12 часов вперёд, имея фактические наблюдения за предыдущие пол дня"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.linear_model import LinearRegression\n",
    "\n",
    "X_train, X_test, y_train, y_test = prepareData(\n",
    "    dataset.Users, test_size=0.3, lag_start=12, lag_end=48\n",
    ")\n",
    "lr = LinearRegression()\n",
    "lr.fit(X_train, y_train)\n",
    "prediction = lr.predict(X_test)\n",
    "plt.figure(figsize=(15, 7))\n",
    "plt.plot(prediction, \"r\", label=\"prediction\")\n",
    "plt.plot(y_test.values, label=\"actual\")\n",
    "plt.legend(loc=\"best\")\n",
    "plt.title(\n",
    "    \"Linear regression\\n Mean absolute error {} users\".format(\n",
    "        round(mean_absolute_error(prediction, y_test))\n",
    "    )\n",
    ")\n",
    "plt.grid(True);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Получилось достаточно неплохо, даже отбора признаков модель ошибается, в среднем, на 3K пользователей в час, и это учитывая огромный выброс в середине тестового ряда.\n",
    "\n",
    "Также можно провести оценку модели на кросс-валидации, тому же принципу, что был использован ранее. Для этого воспользуемся функцией (с небольшими модификациями), предложенной в посте [Pythonic Cross Validation on Time Series](http://francescopochetti.com/pythonic-cross-validation-time-series-pandas-scikit-learn/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     0
    ]
   },
   "outputs": [],
   "source": [
    "def performTimeSeriesCV(X_train, y_train, number_folds, model, metrics):\n",
    "    print(\"Size train set: {}\".format(X_train.shape))\n",
    "\n",
    "    k = int(np.floor(float(X_train.shape[0]) / number_folds))\n",
    "    print(\"Size of each fold: {}\".format(k))\n",
    "\n",
    "    errors = np.zeros(number_folds - 1)\n",
    "\n",
    "    # loop from the first 2 folds to the total number of folds\n",
    "    for i in range(2, number_folds + 1):\n",
    "        print()\n",
    "        split = float(i - 1) / i\n",
    "        print(\n",
    "            \"Splitting the first \" + str(i) + \" chunks at \" + str(i - 1) + \"/\" + str(i)\n",
    "        )\n",
    "\n",
    "        X = X_train[: (k * i)]\n",
    "        y = y_train[: (k * i)]\n",
    "        print(\n",
    "            \"Size of train + test: {}\".format(X.shape)\n",
    "        )  # the size of the dataframe is going to be k*i\n",
    "\n",
    "        index = int(np.floor(X.shape[0] * split))\n",
    "\n",
    "        # folds used to train the model\n",
    "        X_trainFolds = X[:index]\n",
    "        y_trainFolds = y[:index]\n",
    "\n",
    "        # fold used to test the model\n",
    "        X_testFold = X[(index + 1) :]\n",
    "        y_testFold = y[(index + 1) :]\n",
    "\n",
    "        model.fit(X_trainFolds, y_trainFolds)\n",
    "        errors[i - 2] = metrics(model.predict(X_testFold), y_testFold)\n",
    "\n",
    "    # the function returns the mean of the errors on the n-1 folds\n",
    "    return errors.mean()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "performTimeSeriesCV(X_train, y_train, 5, lr, mean_absolute_error)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "На 5 фолдах получили среднюю абсолютную ошибку в 4.6 K пользователей, достаточно близко к оценке качества, полученной на тестовом датасете.\n",
    "\n",
    "Почему бы теперь не попробовать XGBoost\n",
    "<img src=\"https://habrastorage.org/files/754/a9a/26e/754a9a26e59648de9fe2487241a27c43.jpg\"/>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     3
    ]
   },
   "outputs": [],
   "source": [
    "sys.path.append(\"/Users/dmitrys/xgboost/python-package/\")\n",
    "import xgboost as xgb\n",
    "\n",
    "\n",
    "def XGB_forecast(data, lag_start=5, lag_end=20, test_size=0.15, scale=1.96):\n",
    "\n",
    "    # исходные данные\n",
    "    X_train, X_test, y_train, y_test = prepareData(\n",
    "        dataset.Users, lag_start, lag_end, test_size\n",
    "    )\n",
    "    dtrain = xgb.DMatrix(X_train, label=y_train)\n",
    "    dtest = xgb.DMatrix(X_test)\n",
    "\n",
    "    # задаём параметры\n",
    "    params = {\"objective\": \"reg:linear\", \"booster\": \"gblinear\"}\n",
    "    trees = 1000\n",
    "\n",
    "    # прогоняем на кросс-валидации с метрикой rmse\n",
    "    cv = xgb.cv(\n",
    "        params,\n",
    "        dtrain,\n",
    "        metrics=(\"rmse\"),\n",
    "        verbose_eval=False,\n",
    "        nfold=10,\n",
    "        show_stdv=False,\n",
    "        num_boost_round=trees,\n",
    "    )\n",
    "\n",
    "    # обучаем xgboost с оптимальным числом деревьев, подобранным на кросс-валидации\n",
    "    bst = xgb.train(params, dtrain, num_boost_round=cv[\"test-rmse-mean\"].argmin())\n",
    "\n",
    "    # можно построить кривые валидации\n",
    "    # cv.plot(y=['test-mae-mean', 'train-mae-mean'])\n",
    "\n",
    "    # запоминаем ошибку на кросс-валидации\n",
    "    deviation = cv.loc[cv[\"test-rmse-mean\"].argmin()][\"test-rmse-mean\"]\n",
    "\n",
    "    # посмотрим, как модель вела себя на тренировочном отрезке ряда\n",
    "    prediction_train = bst.predict(dtrain)\n",
    "    plt.figure(figsize=(15, 5))\n",
    "    plt.plot(prediction_train)\n",
    "    plt.plot(y_train)\n",
    "    plt.axis(\"tight\")\n",
    "    plt.grid(True)\n",
    "\n",
    "    # и на тестовом\n",
    "    prediction_test = bst.predict(dtest)\n",
    "    lower = prediction_test - scale * deviation\n",
    "    upper = prediction_test + scale * deviation\n",
    "\n",
    "    Anomalies = np.array([np.NaN] * len(y_test))\n",
    "    Anomalies[y_test < lower] = y_test[y_test < lower]\n",
    "\n",
    "    plt.figure(figsize=(15, 5))\n",
    "    plt.plot(prediction_test, label=\"prediction\")\n",
    "    plt.plot(lower, \"r--\", label=\"upper bond / lower bond\")\n",
    "    plt.plot(upper, \"r--\")\n",
    "    plt.plot(list(y_test), label=\"y_test\")\n",
    "    plt.plot(Anomalies, \"ro\", markersize=10)\n",
    "    plt.legend(loc=\"best\")\n",
    "    plt.axis(\"tight\")\n",
    "    plt.title(\n",
    "        \"XGBoost Mean absolute error {} users\".format(\n",
    "            round(mean_absolute_error(prediction_test, y_test))\n",
    "        )\n",
    "    )\n",
    "    plt.grid(True)\n",
    "    plt.legend()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "XGB_forecast(dataset, test_size=0.2, lag_start=12, lag_end=48)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Те же 3 K пользователей в средней абсолютной ошибке, и неплохо пойманные аномалии на тестовом датасете. Конечно, чтобы уменьшить ошибку, еще можно повозиться с параметрами, настроить при необходимости регуляризацию, отобрать признаки, понять, на сколько лагов нужно уходить вглубь истории и т.д. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Заключение\n",
    "\n",
    "Мы познакомились с разными методами и подходами к анализу и прогнозированию временных рядов. К сожалению, или к счастью, серебряной пули для решения такого рода задач пока не появилось. Методы, разработанные в 60-е годы прошлого века, (а некоторые и в начале 19-го), по-прежнему пользуются популярностью наравне с неразобранными в рамках данной статьи LSTM или RNN. Отчасти это связано с тем, что задача прогнозирования, как и любая другая задача, возникающая в процессе работы с данными - во многом творческая и уж точно исследовательская. Несмотря на обилие формальных метрик качества и способов оценки параметров, для каждого временного ряда часто приходится подбирать и пробовать что-то своё. Не последнюю роль играет и баланс между качеством и трудозатратами. Не раз уже упоминавшаяся здесь SARIMA-модель хотя и демонстрирует выдающиеся результаты при должной настройке, может потребовать не одного часа ~~танцев с бубном~~ манипуляций с рядом, в то время как простенькую линейную регрессию можно соорудить за 10 минут, получив при этом более-менее сравнимые результаты."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Полезные ресурсы\n",
    "\n",
    "- [Онлайн учебник](https://people.duke.edu/~rnau/411home.htm) курса по продвинутому статистическому прогнозированию университета Duke - разобраны всевозможные сглаживания, линейные модели и ARIMA модели \n",
    "- Статья [Comparison of ARIMA and Random Forest time series models for prediction of avian influenza H5N1 outbreaks](https://bmcbioinformatics.biomedcentral.com/articles/10.1186/1471-2105-15-276) - одна из немногих, где активно защищается позиция случайного леса в задачах по прогнозированию временных рядов\n",
    "- Статья [Time Series Analysis (TSA) in Python - Linear Models to GARCH](http://www.blackarbs.com/blog/time-series-analysis-in-python-linear-models-to-garch/11/1/2016) семействе моделей ARIMA и их применении для моделирования финансовых показателей (Brian Christopher)"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
